Applications running on computer systems typically invoke multiple processes in a course of execution. Within a program, one process may call another or call itself (in recursion) in order to effect program execution. A stack is an area of memory allocated to last-in-first-out (LIFO) accesses of state information. As one process switches to another, the state of a first process is saved to preserve an operational context before switching to a new context for a called process. An operational context may be composed of return addresses, values in general purpose or special purpose registers, parameters, automatic variables or data generated in the execution of a process. A plurality of context values constitute a state of a machine and are quantities required by an executing process up to a point that another process is called. A case where a first process calls another, where the operational state of the calling process is saved to a stack, is termed context switching. A storage structure defined in memory for capturing all of the operational quantities associated with the execution state of a machine is termed an activation record or a stack frame.
After being called, a newly executing process may have need to store and retrieve certain data or parameters to and from stack memory during the course of execution. PUSH and POP instructions are used to store and retrieve respectively. Data transactions brought about by the PUSH and POP instructions are carried out in general memory within the stack. Some stacks progress within upper memory from high locations to lower locations and therefore grow down in memory addresses during use. In the case of a grow-down stack, the top of the stack moves lower in memory locations as data is stored and retrieved.
In order for a called process to maintain execution within a portion of memory appropriate to a present execution context, a number of PUSH instructions executed is greater than or equal to the number of POP instructions. In an executing program a new context is formed at a procedure call. After storing a stack frame, as may be required after the context switch, a next stack memory access is due to a PUSH instruction in typical operation. Data is put into the stack before any retrieval is performed. Additionally, the number of POP instructions does not exceed the number of PUSH instructions or else an excessive number of POP instructions pull data from a prior context or from relating memory to a different process. An excessive number of POP instructions also updates a pointer to a next writable stack location (i.e. a stack pointer) and opens an opportunity for data from another context to be overwritten. In a case where more PUSH instructions are executed than there is memory space allotted to stack storage, an access out of range for the stack memory or a wrap around condition may result. Generally, in most processors, the out of range condition or memory wrap is called a stack overflow. A stack overflow triggers an exception condition and may cause execution to jump to a debug monitor routine to resolve a cause of the problem condition.
To explain the operation of PUSH and POP instructions, a PUSH instruction increments the stack pointer by 1. Next, the contents of a variable indicated directly in a PUSH instruction are copied into an internal RAM location addressed by the stack pointer. Operationally the PUSH instruction is:
PUSH (onto stack):
(SP) ←(SP)+1
((SP)) ←(direct)
where the symbology is defined as:
← . . . is replaced by . . .
( . . . ) the contents of . . .
(( . . . )) the data pointed to by . . .
direct the value (variable) referenced directly in the instruction
A POP instruction retrieves the contents of the internal RAM location addressed by the stack pointer and the stack pointer is decremented by 1. The value retrieved is transferred to a directly addressed byte indicated in the instruction. Operationally the POP instruction is:
POP (from stack):
(direct ) ←((SP))
(SP) ←(SP)−1
Proper stack maintenance is crucial to correct execution of a program and for correct transactions involving operands. In view of a general capability existing to handle stack overflow, what is needed is an approach to stack underflow that is economical, transparent to a user, and allows for debug operations to be triggered and traced from an underflow occurrence.